package me.mingshan.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
 * <p>
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 * 示例 1:
 * <p>
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 * @Author: mingshan
 * @Date: Created in 17:10 2018/9/16
 */
public class L_3_LengthOfLongestSubstring {

    public static void main(String[] args) {
        String a = "abcabcbb";

        //System.out.println(lengthOfLongestSubstring(a));

        String a2 = "a";

        //System.out.println(lengthOfLongestSubstring(a2));

        String a3 = "ab";

        //System.out.println(lengthOfLongestSubstring(a3));

        String a4 = "aab";

        //System.out.println(lengthOfLongestSubstring(a4));

        String a5 = "abcdc";
        System.out.println(lengthOfLongestSubstring(a5));
    }

    /**
     * 暴力求解
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        if (s.length() == 1) {
            return 1;
        }

        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            Map<Character, Integer> map = new HashMap<>();
            map.put(s.charAt(i), 1);

            for (int j = i + 1; j < s.length(); j++) {
                map.merge(s.charAt(j), 1, Integer::sum);

                if (map.get(s.charAt(j)) > 1) {
                    result = Math.max(result, j - i);
                    break;
                }

                // 如果j是最后一个字符，则将结果更新
                if (j == s.length() - 1) {
                    result = Math.max(result, j - i + 1);
                    break;
                }
            }
        }

        return result;
    }

    /**
     * 滑动窗口
     *
     * 定义窗口的左边界和右边界，初始时，左边界和右边界都指向字符串的开头。
     *
     * 移动右边界，保证窗口内一直没有重复的字符。
     * 如果在移动右边界时，出现了重复的字符，则移动左边界，直到重复的字符不再存在。
     *
     *
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        if (s.length() == 1) {
            return 1;
        }

        Map<Character, Integer> map = new HashMap<>();

        int result = 0;
        int left = 0;
        int right = 0;

        for (; right < s.length(); right++) {
            char c = s.charAt(right);

            map.put(c, map.getOrDefault(c, 0) + 1);

            if (map.get(c) > 1) {
                // 判断需要不需要出窗口
                // 如果发现当前的字符串出现过了，则需要将左边界移动
                while (map.get(c) > 1) {
                    result = Math.max(result, right - left);

                    char leftChar = s.charAt(left);
                    map.put(leftChar, map.get(leftChar) - 1);
                    left++;
                }
            } else {
                if (right == s.length() - 1) {
                    result = Math.max(result, right - left + 1);
                }
            }
        }

        return result;
    }
}
